﻿/*
 *Copyright (C) 2012 Hassan Tariq (mailto:delegatex@live.com).
 *Written for Mathos project on Codeplex. (http://mathos.codeplex.com).
 *All Rights Reserved.
*/

//The tokenizer is no where completed. It will require considerable amount of time if we want a powerful syntax. The unary operators are working fine but there are certain rules that must be forced (Actually, this is the task of the parser to define the meaning, but I am doing as much as I can in the tokenizer so parser has less to worry about). Only two operators are implemented (partially) at the moment (+ and -). Parenthesis are in working position too. I will keep working on the tokenizer. The code is fully commented, so you won't have much problem seeing the big picture. If you are editing it, please make sure you comment everyline with some reasoning no matter how obvious it is. Things go out of hand quickly in such complex problems. I have also created a Windows Forms Project named MathParserTest that contains a form with some controls to test the tokenizer. Test it and report the probelms either on project page, or comment out in the class at the bottom. ~Hassan (DelegateX)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using MathParserDemo.TokenizerExceptions;
namespace MathParserDemo
{
    /// <summary>
    /// Contains constant for identifying token types.
    /// </summary>
    public enum TokenType
    {
        AdditionOperator, // +
        SubtractionOperator, // -
        Multiplicationoperator,// *
        DivisionOperator, // /
        ModulusOperator, // %
        PowerOfOperator, // ^
        UnaryAddition, //++
        UnaryNegation, //--
        LessThan, // <
        GreaterThan, // >
        LessThanEqualTo, // <=
        GreaterThanEqualTo, // >=
        NotEqualsTo, // !=
        ConditionalAND, // &&
        ConditionalOR, // ||
        Equals, // =
        AddThenAssign, // +=
        SubtractThenAssign, // -=
        MultiplyThenAssign, // *=
        DivideThenAssign, // /=
        ModulusThenAssign, // %=
        PowerThenAssign, // ^=
        Identifier, // e.g: x
        IdentifierAssignment, // =
        Bracket, // ()
        Brace, // {} //Will use for defining a custom function.
        Angle, // <> (For defining a collection.)
        Indexer, // [] (For referring to an item in a collection.)
        Function, // e.g: MultiplyThenDivide (Basically, an identifier but becomes a function if brackets are found immediately after it.)
        Number, // This represents all types of numbers. e.g: int, float, double.
    }
    /// <summary>
    /// Constains constants for identifying the priority of a token. The order of precedence is from highest to lowest. Precedence can be controlled using parenthesis (bracket) which has the highest prcedence.
    /// </summary>
    public enum TokenPriority
    {
        Parenthesis = 10, // () has the highest priority.
        Function = 9, // e.g: MultiplyThenDivide
        Indexer = 9, // []
        Unary = 8, // ++, -- 
        Multiplicative = 7, // *, /, %, ^
        Additive = 6, // +, -
        Relational = 5, // <, >, <=, >=, !=
        Equality = 4, // ==
        ConditionalAND = 3, //&&
        ConditionalOR = 2, // ||
        Assignment = 1, // =, +=, -=, *=, /=, %=, ^= Assignment is performed in the last and hence has the lowest priority.
        Other = 0 // All tokens which have nothing to do with precedence lie in this category.
    }
    /// <summary>
    /// Represents a single token that is consumed by the tokenizer as it scans the source.
    /// </summary>
    public struct Token
    {
        
        public TokenType TType; //Type of our token.
        public object Value; //Value of our token.
        public TokenPriority Priority; //Priority of our token. This is required to implement prioritized math expressions. e.g: (2+4 - (8/2)). 8/2 will be evaluated first.
        public int Column; //Would be helpful for displaying the location of token in user interface.
    }
    /// <summary>
    /// Provides static methods to tokenize a line for the parser.
    /// </summary>
    public class Tokenizer
    {
        /// <summary>
        /// Reads a single line requested by the parser and tokenizes the line. If the tokenization is successful (i.e; it contains at-least one token), it returns a generic list of tokens. An empty list is returned otherwise.
        /// </summary>
        /// <param name="Line">The line of code that needs to be tokenized.</param>
        public static List<Token> Tokenize(string Line)
        {
            
            if (string.IsNullOrEmpty(Line.Trim())) //Check if the line is empty.
                return new List<Token>() { }; //We have an empty line. Return a new empty list.
            //I wish I could use Regex but it can't parse patterns to indefinite depths :(
            
            List<Token> TokenList = new List<Token>(); //Create a list to store the tokens.
            Token T = new Token(); //Store the properties of the current token to be added to the list.

            bool InBracket = false; //Flag that checks if we are in a bracket.
            bool InBrace = false; //Flag that checks if we are in a brace.
            bool InAngle = false; //Flag that checks if we are in an angle bracket.
            bool UnaryAddition = false;
            bool UnarySubtraction = false;
            int OpenedBrackets = 0, ClosedBrackets = 0; //Keeps track of the opening and closing characters of a bracket. This is used to balance the brackets.
            int OpenedBraces = 0, ClosedBraces = 0; //Keeps track of the opening and closing characters of a brace. This is used to balance the braces.
            int OpenedAngles = 0, ClosedAngles = 0; //Keep track of the opening and closing characters of an angle. This is used to balance the angles.

            string TemporaryBuffer = ""; //Stores the value temporarily for processing before it is ready to be added to token list.

            for (int NextChar = 0; NextChar < Line.Length; NextChar++) //Loop through every character.
            {
                char CVal = Line[NextChar]; //Current character being processed.
                if (CVal == '(') //If the character is an opening bracket
                {
                    if (T.TType == TokenType.Identifier && OpenedBrackets == 0) //If our previous token was an identifier and this is the first bracket right after the identifier then it means that our identifier should be turned into a function. To do this we simply leave the buffer with the name of the identifier and overwrite the previous token in the next line so it becomes a part of the brackets. We also set the type to function so we can recognize it later as such in the semantic analysis phase.
                    {
                        T = new Token(); //Initialize a new token and assign it to T.
                        T.TType = TokenType.Function; //Set the type to Function.
                    }
                    else
                    {
                        //This checks if there is anything pending to be added to the list.
                        if (OpenedBrackets == 0)  //Make sure we are outside the brackets.
                        {
                            if (TemporaryBuffer != "") //Before adding to the list make sure that we have something to add.
                            {
                                T.Value = TemporaryBuffer; //Assign temporary buffer to the token value.
                                TokenList.Add(T); //Add the token to token list.
                                TemporaryBuffer = ""; //Reset the buffer.
                            }
                        }
                    }
                    if (NextChar == Line.Length-1) //Make sure its not the last character in the line. If it is, that means we have no matching closing bracket.
                    {
                        throw new TokenizerExceptions.IncompletePattern("No closing bracket(s) could be found to match the opening bracket(s)."); //We were unable to find the closing bracket. Throw an exception.
                        return new List<Token>(); //Return an empty list incase the exception is handled.
                    }
                    OpenedBrackets++; //Increment the opened bracket count.
                    InBracket = true; //Flag that indicates we are in a bracket. This means we include all the characters until a matching closing bracket is not found.
                    TemporaryBuffer += "("; //Append the opening bracket to the buffer.
                    continue; //No need to go through rest of the loop. Contine with next iteration.
                }
                if (CVal == ')') //If the character is a closing bracket.
                {
                    ClosedBrackets++; //Increment the closed bracket count.
                    if ((OpenedBrackets != ClosedBrackets) && (NextChar == Line.Length-1)) //If we have reached the end of line and the number of opened brackets is not equal to the number of closed brackets.
                    {
                        throw new TokenizerExceptions.IncompletePattern("No match between opened bracket(s) and the closed bracket(s) was found."); //Unable to balance the brackets. Throw an exception.
                        return new List<Token>(); //Return an empty list incase the exception is handled.
                    }
                    TemporaryBuffer += ")"; //Append closing bracket character to buffer.
                    if (OpenedBrackets == ClosedBrackets) //If the brackets are balanced.
                    {
                        if (!(T.TType == TokenType.Function)) //If we don't have a pending Token which is marked as a Function, then we simply set the token properties to a normal parenthesis.
                        {
                            T = new Token(); //Create a new token.
                            T.TType = TokenType.Bracket; //Set the type to bracket.
                            T.Value = TemporaryBuffer; //Assign the buffer to its value.
                            T.Priority = TokenPriority.Parenthesis; //Set priority to parenthesis.
                        }
                        else //If there's some text in the buffer and it the token is marked as a Function, then we set the token properties to that of a function.
                        {
                            T = new Token(); //Create a new token.
                            T.TType = TokenType.Function; //Set the type to Function.
                            T.Value = TemporaryBuffer; //Assign the buffer to its value.
                            T.Priority = TokenPriority.Function; //Set priority to Function.
                        }
                        T.Column = NextChar; //Set the column to index of the current character being read.
                        TokenList.Add(T); //Add the token to the list of tokens.
                        TemporaryBuffer = ""; //Reset the buffer.
                        InBracket = false; //We are no longer in the brackets. Continue with regular tokenization.
                        OpenedBrackets = 0; //Reset the opened brackets.
                        ClosedBrackets = 0; //Reset the closed brackets.
                    }
                }
                if (InBracket && (OpenedBrackets != ClosedBrackets) && (NextChar == Line.Length - 1)) //If we have reached the end of line and the number of opened brackets is not equal to the number of closed brackets.
                {
                    throw new TokenizerExceptions.IncompletePattern("No match between opened bracket(s) and the closed bracket(s) was found."); //Unable to balance the brackets. Throw an exception.
                    return new List<Token>(); //Return an empty list incase the exception is handled.
                }
                if (InBracket) //If we are in inside a bracket.
                {
                    if(!(CVal==')') || !(char.IsWhiteSpace(CVal))) //We don't need to append the closing bracket because we are already appending it when the scanner encounters it.
                    TemporaryBuffer += CVal; //Append the current character to the buffer.
                    continue; //Skip the rest of the loop and start the next iteration.
                }
                if (char.IsWhiteSpace(CVal)) //Check if the current character is a whitespace. If it is, then it means it has no meaning for us and we simply check if there is any pending token to be added to the list and add it.
                {
                    if (TemporaryBuffer != "") //Make sure we got something to add to the list.
                    {
                        T.Value = TemporaryBuffer; //Assign the buffer to its value.
                        TokenList.Add(T); //Add the token to token list.
                        TemporaryBuffer = ""; //Reset the buffer.
                        continue; //No need to go through rest of the loop. Nothing is depended on a whitespace.
                    }
                }
                if (CVal == '+') //Check to see if the character being observed is an addition operator. If it is, then we have a few things to do. First, we check if we have a pending token to be added to the list that is marked as an identifier. This concerns the addition operator because we need to keep the identifier together with the unary operator (if we find one). If we don't find it, we add the pending token to the list. The next step is to check if there is an addition operator right after this addition operator, and if we have it, we place a few checks and do some processing to make sure the rules are followed. The possible valid unary operations are: ++x, x++, x+++++y (++x is separated, then the next + is separated, then in the end ++y is seperated). Invalid unary operations are: +++x, x+++ (this applies if there are no more valid tokens to read). Incase of violation of these rules, we throw an exception.
                {
                    if (TemporaryBuffer != "") //Check if the buffer is not empty.
                    {
                        if (T.TType == TokenType.Identifier) //If we have an identifier than there is a possibility that there can be an addition operator after this addition operator. We check this next.
                        {
                            if (NextChar != Line.Length - 1) //Make sure we don't run out of tokens. We need at least one more token ahead of this token before we goto the next check.
                            {
                                if (Line[NextChar + 1] == '+') //We now see if the next character (NextChar+1) is an addition operator.
                                {
                                    T = new Token(); // Initialize a new token and assign it to T. This is to make sure that we don't repeat all of this process in the next iteration.
                                }
                                else //We haven't found an addition operator after this addition operator. Add the identifier to the token list.
                                {
                                    T.Value = TemporaryBuffer; //Assign the buffer to its value.
                                    TokenList.Add(T); //Add the token to token list.
                                    TemporaryBuffer = ""; //Reset the buffer.
                                }
                            }
                        }
                        else //We have a pending token but it is not an identifier. Add it to the token list.
                        {
                            T.Value = TemporaryBuffer; //Assign the buffer to its value.
                            TokenList.Add(T); //Add the token to token list.
                            TemporaryBuffer = ""; //Reset the buffer.
                        }
                    }
                    //Now that we have dealt with the pending tokens, we need to check for the possibility of a unary token.
                    if (NextChar != Line.Length - 1) //Make sure we have atleast one character to process ahead of the current character / token.
                    {
                        //Before we tokenize the unary operator, we need to make sure the rules are followed.
                        if (NextChar != 0 && NextChar != Line.Length - 1) //Make sure we have a character before this addition operator and a charactter ahead of this addition operator.
                        {
                            if (Line[NextChar - 1] == '+' && Line[NextChar + 1] == '+') //If there is an addition operator before and after this one, the rule is violated. We need some operand so that we can apply the our operator on it.
                            {
                                throw new IncompletePattern("Too many addition operators without appropriate number of operands in surrounding."); //The rule was violated. Throw an exception.
                                return new List<Token>(); //Return an empty List.
                            }
                        }
                        if (Line[NextChar + 1] == '+') //If the next character is an addition operator too.
                        {
                            if (NextChar != Line.Length - 2) //See if we got two more characters ahead.
                            {
                                if (!(char.IsLetter(Line[NextChar + 2]))) //If the character after the next character is not a number, then it means we can split the middle addition operator (this one). This way, we can have operations between two unary operators.
                                {
                                    if (!(char.IsLetter(Line[NextChar - 1]))) //If the previous character wasn't a letter, then we can separate this addition operator and add it to the list as a normal addition operator.
                                    {
                                        T = new Token(); //Create a new token.
                                        T.TType = TokenType.AdditionOperator; //Set the type to AdditionOperator.
                                        T.Priority = TokenPriority.Additive; //Set priority to Additive.
                                        T.Value = "+"; //Hardcode the value to +
                                        T.Column = NextChar; //Set the column to the current position of the line.
                                        TokenList.Add(T); //Add the token to the list.
                                        TemporaryBuffer = ""; //Reset the buffer.
                                        continue; //No need to go through rest of the loop. Continue with the next iteration.
                                    }
                                }
                            }
                            //If there was any separation to be performed, it has been done above. So, simply prepend the buffer (identifier) to a unary operator (++) and add it to the list.
                            T = new Token(); //Create a new token.
                            T.TType = TokenType.UnaryAddition; //Set the type to UnaryAddtion.
                            T.Priority = TokenPriority.Unary; //Set the priority to Unary.
                            T.Value = TemporaryBuffer + "++"; //Prepend the buffer to ++
                            T.Column = NextChar; //Set the column to the current position of the line.
                            TokenList.Add(T); //Add the token to the token list.
                            TemporaryBuffer = ""; //Reset the buffer.
                            UnaryAddition = true; //It was a unary addition, so set the UnaryAddition to true. If we encounter a letter in the next token, this would be helpful. (Prefix unary addition).
                            NextChar += 1; //We already checked the next addition operator and merged it with this addition operator, so we just skip the next character of the source / line.
                            continue; //No need to go through rest of the loop. Continue with the next iteration.
                        }
                        else //We don't have an addition operator ahead of this addition operator. So will simply add this addition operator to the list.
                        {
                            T = new Token(); //Create a new token.
                            T.TType = TokenType.AdditionOperator; //Set the type to AdditionOperator.
                            T.Priority = TokenPriority.Additive; //Set the priority to Additive.
                            T.Value = "+"; //Hardcode the value to +
                            T.Column = NextChar; //Set the column to the current position of the line.
                            TokenList.Add(T); //Add the token to the list.
                            TemporaryBuffer = ""; //Reset the buffer.
                        }
                    }
                    else //This was the last character of the line and though we should be throwing an exception here, we just add the addition operator to the list as is. This is to allow the feature of multiline code. (Just incase we decide to support it.)
                    {
                        T = new Token(); //Create a new token.
                        T.TType = TokenType.AdditionOperator; //Set the type to AdditionOperator.
                        T.Priority = TokenPriority.Additive; //Set the priority to Additive.
                        T.Value = "+"; //Hardcode the value to +
                        T.Column = NextChar; //Set the column to the current position of the line.
                        TokenList.Add(T); //Add the token to the list.
                        TemporaryBuffer = ""; //Reset the buffer.
                    }
                }
                if (char.IsDigit(CVal)) //If the current character is a digit
                {
                    if (TemporaryBuffer == "") //Make sure we don't have an existing token to add to the list.
                    {
                        T = new Token(); //Create a new token.
                        T.Priority = TokenPriority.Other; //Set the priority to other (none).
                        T.TType = TokenType.Number; //Set the type to Number.
                    }
                    TemporaryBuffer += CVal; //Append the current digit to the buffer.S
                }
                if (char.IsLetter(CVal)) //If we have a letter (identifier for us).
                {
                    if (TemporaryBuffer == "") //Make sure we don't have an existing token to add to the list.
                    {
                        T = new Token(); //Initialize a new token.
                        T.TType = TokenType.Identifier; //At this point, it is an identifier because we don't know if there are brackets coming after it. If there are any brackets afterwards, we will change the type to a Function.
                    }
                    if (UnaryAddition) //Check if the previous token was a unary operator. If so, change the type to unary addition and prepend ++ to the buffer. Also, remove the unary operator that was added to the list. Finally, set unary addition flag to false.
                    {
                        T.TType = TokenType.UnaryAddition; //Set token type to unary addition.
                        T.Priority = TokenPriority.Unary; //Set token priority to Unary.
                        TemporaryBuffer = "++" + TemporaryBuffer; //Prepend ++ to the buffer.
                        TokenList.RemoveAt(TokenList.Count - 1); //Remove the last unary operator from the token list.
                        UnaryAddition = false; //Reset the UnaryAddition flag.
                    }
                    if (UnarySubtraction) //Check if the previous token was a unary operator. If so, change the type to unary subtraction and prepend -- to the buffer. Also, remove the unary operator that was added to the list. Finally, set unary subtraction flag to false.
                    {
                        T.TType = TokenType.UnaryNegation; //Set token type to unary negation.
                        T.Priority = TokenPriority.Unary; //Set token priority to Unary.
                        TemporaryBuffer = "--" + TemporaryBuffer; //Prepend -- to the buffer.
                        TokenList.RemoveAt(TokenList.Count - 1); //Remove the last unary operator from the token list.
                        UnarySubtraction = false; //Reset the UnarySubtraction flag.
                    }
                    TemporaryBuffer += CVal; //Append the character to the buffer.
                }
                if (NextChar == Line.Length - 1) //If after all the above operations, there is a pending token to be added, add it now but only if it is the last character of the line.
                {
                    if (TemporaryBuffer != "") //Make sure we got something to add to the list of tokens.
                    {
                        T.Value = TemporaryBuffer; //Add buffer to token's value.
                        TokenList.Add(T); //Add the token to the list.
                        TemporaryBuffer = ""; //Reset the buffer.
                    }
                }
                UnaryAddition = false; //We are no longer dealing with any unary operation, so reset the UnaryAddition flag.
                UnarySubtraction = false; //We are no longer dealing with any unary operation, so reset the UnarySubtraction flag.
            }
            return TokenList; //Return the token list to the caller.
        }
    }
}